package everyday.apr;

/**
 * 780. 到达终点
 */
public class Day9 {
    public static void main(String[] args) {
        System.out.println(reachingPoints(1,1,3,5));
        System.out.println(reachingPoints(1,1,2,2));
        System.out.println(reachingPoints(1,1,1,1));
    }

    /**
     * 更相减损法和辗转相除法，反向求解（改变目标）
     */
    public static boolean reachingPoints(int sx, int sy, int tx, int ty) {
        while (tx > sx && ty > sy && tx != ty) {
            if (tx > ty) {
                tx %= ty;
            } else {
                ty %= tx;
            }
        }
        if (tx == sx && ty == sy) {
            return true;
        } else if (tx == sx) {
            return ty > sy && (ty - sy) % tx == 0;
        } else if (ty == sy) {
            return tx > sx && (tx - sx) % ty == 0;
        } else {
            return false;
        }
    }

    /**
     * 递归，数据一大，直接StackOverflowError
     */
    public boolean reachingPoints1(int sx, int sy, int tx, int ty) {
        if (sx > tx || sy > ty) return false;
        if (sx == tx && sy == ty) return true;
        return reachingPoints(sx + sy, sy, tx, ty) || reachingPoints(sx, sx + sy, tx, ty);
    }
}
